#include "AABB.h"
#include <iostream>

#define MIN(a, b) (a * (a < b) + b * (a >= b))
#define MAX(a, b) (a * (a >= b) + b * (a < b))


using namespace std;

bool AABB::intersect(Ray *r) {
    float gmin, gmax;
    float xmin, ymin, zmin, xmax, ymax, zmax;

    xmin = ymin = zmin = FLT_MIN;
    xmax = ymax = zmax = FLT_MAX;

    if ((r->point.x > max.x && r->d.x > 0 ||
        r->point.x < min.x && r->d.x < 0) &&
        (r->point.y > max.y && r->d.y > 0 ||
        r->point.y < min.y && r->d.y < 0) &&
        (r->point.z > max.z && r->d.z > 0 ||
        r->point.z < min.z && r->d.z < 0)) {
        
        return false;
    }


    xmax = (max.x - r->point.x) / r->d.x;
    ymax = (max.y - r->point.y) / r->d.y;
    zmax = (max.z - r->point.z) / r->d.z;
    xmin = (min.x - r->point.x) / r->d.x;
    ymin = (min.y - r->point.y) / r->d.y;
    zmin = (min.z - r->point.z) / r->d.z;

    if (xmax < xmin) {
        xmax = xmax + xmin;
        xmin = xmax - xmin;
        xmax = xmax - xmin;
    }
    
    if (ymax < ymin) {
        ymax = ymax + ymin;
        ymin = ymax - ymin;
        ymax = ymax - ymin;
    }

    if (zmax < zmin) {
        zmax = zmax + zmin;
        zmin = zmax - zmin;
        zmax = zmax - zmin;
    }

//    gmax = std::min(std::min(xmax, ymax), zmax);
    gmax = MIN(MIN(xmax, ymax), zmax);
//    gmin = std::max(std::max(xmin, ymin), zmin);
    gmin = MAX(MAX(xmin, ymin), zmin);

    return gmin < gmax;
}

AABB *AABB::merge(AABB *r) {
    AABB *ret;

    ret = new AABB();

    ret->left = this;
    ret->right = r;

    ret->min = vec3(
            std::min(min.x, r->min.x),
            std::min(min.y, r->min.y),
            std::min(min.z, r->min.z));
    ret->max = vec3(
            std::max(max.x, r->max.x),
            std::max(max.y, r->max.y),
            std::max(max.z, r->max.z));

    return ret;
}

float AABB::compare(AABB *other, int direction) {
    return this->min[direction] - other->min[direction];  
}

bNode *sort(bNode *boxes, int direction, int num) {
    /* horray for bad naming convention */
    /* temp1 is for sorting the former half of boxes,
     * temp2 is for sorting the latter half of boxes
     * the walk variables are for merging the lists */
    bNode *temp1, *temp2, *walk1, *walk2;
    bNode *retHead = NULL, *retTemp = NULL;
    int count;
    int i, j;
/*    printf("NUM: %d\n", num);
    boxes->print(1);
    fflush(stdout);
*/
    if (num == 2) {
        temp1 = new bNode();
        if (boxes->box->compare(boxes->next->box, direction) > 0) {
            temp1->box = boxes->next->box;
            temp1->next = new bNode(NULL, boxes->box);
        }
        else {
            temp1->box = boxes->box;
            temp1->next = new bNode(NULL, boxes->next->box);
        }

        return temp1;
    }
    else if (num <= 1) {
        temp1 = new bNode(NULL, boxes->box);
        return temp1;
    }

    count = 0;
    temp2 = boxes;
    while (count < num / 2) {
        temp2 = temp2->next;
        count++;
    }

    //printf("num: %d\tnum/2: %d\t(num + 1)/2: %d\n", num, num/2, (num + 1) / 2);
    i = j = 0;
//    boxes->print(0);
//    printf("Left\n");
    temp1 = sort(boxes, direction, num / 2);
//    boxes->print(0);
//    printf("Right\n");
    temp2 = sort(temp2, direction, (num + 1) / 2);

    walk1 = temp1;
    walk2 = temp2;

    retHead = new bNode();
    retTemp = retHead;

    while (i < num / 2 || j < num - num / 2) {
        if (i >= num / 2) {
            retTemp->next = new bNode(NULL, walk2->box);
            j++;
            walk2 = walk2->next;
            retTemp = retTemp->next;
        }
        else if (j >= num - num / 2) {
            retTemp->next = new bNode(NULL, walk1->box);
            i++;
            walk1 = walk1->next;
            retTemp = retTemp->next;
        }
        else {
            if (walk1->box->compare(walk2->box, direction) < 0) {
                retTemp->next = new bNode(NULL, walk1->box);
                i++;
                walk1 = walk1->next;
                retTemp = retTemp->next;
            }
            else {
                retTemp->next = new bNode(NULL, walk2->box);
                j++;
                walk2 = walk2->next;
                retTemp = retTemp->next;
            }
        }
    }

    delete temp1;

    temp2 = retHead->next;
    retHead->next = NULL;

//    delete retHead;
    return temp2;
}


AABB *generateBoxes(bNode *boxes, int sortDirection, int num) {
    bNode *sortList, *walkList;
    AABB *l, *r;
    int count = 0;

    if (num == 2) {
        return boxes->box->merge(boxes->next->box);
    }
    else if (num == 1) {
        return boxes->box;
    }

    sortList = sort(boxes, sortDirection, num);
//    delete boxes;

    walkList = sortList;
    while (count < num / 2) {
        walkList = walkList->next;
        count++;
    }

    l = generateBoxes(sortList, (sortDirection + 1) % 3, num / 2);
    r = generateBoxes(walkList, (sortDirection + 1) % 3, (num + 1) / 2);

    l = l->merge(r);

    return l;
}

void AABB::print() {
    static int count = 0;

    /*if (isLeaf) {
    cout << ++count << endl;
        return;
    }*/
    printf("BOX:\tmin: <%f, %f, %f>\tmax: <%f, %f, %f>\n",
            min.x, min.y, min.z, max.x, max.y, max.z);
    /*if (isLeaf) {
        g->print();
    }
    else {
        printf("left\t");
        left->print();
       // printf("right\t");
        right->print();
    }*/

}


